import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 84. 柱状图中最大的矩形
 */
public class Solution_84 {
    /**
     * 方法二：单调栈 + 哨兵
     * <p>
     * liweiwei 题解
     * <p>
     * 时间复杂度：O(N)
     * 空间复杂度：O(N)
     */
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if (len == 0) {
            return 0;
        }
        if (len == 1) {
            return heights[0];
        }

        int ans = 0;
        int[] newHeights = new int[len + 2];
        newHeights[0] = 0;
        for (int i = 0; i < len; i++) {
            newHeights[i + 1] = heights[i];
        }
        newHeights[len + 1] = 0;
        len += 2;
        heights = newHeights;

        Deque<Integer> stack = new ArrayDeque<Integer>();
        // 先放入哨兵，在循环里就不用做非空判断
        stack.push(0);
        for (int i = 1; i < len; i++) {
            while (heights[i] < heights[stack.peek()]) {
                int cur = heights[stack.pop()];
                int width = i - stack.peek() - 1;
                ans = Math.max(ans, cur * width);
            }
            stack.push(i);
        }
        return ans;
    }

    /**
     * 方法一：暴力美学（超时）
     * <p>
     * 依次遍历柱形的高度，对于每一个高度分别向两边扩散，求出以当前高度为矩形的最大宽度多少
     * <p>
     * 时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     */
    public int largestRectangleArea1(int[] heights) {
        int len = heights.length;
        if (len == 0) {
            return 0;
        }

        int ans = 0;
        for (int i = 0; i < len; i++) {
            int cur = heights[i];
            // 找左边最后一个大于等于 heights[i] 的下标
            int left = i;
            while (left > 0 && heights[left - 1] >= cur) {
                left--;
            }
            // 找右边最后一个大于等于 heights[i] 的下标
            int right = i;
            while (right < len - 1 && heights[right + 1] >= cur) {
                right++;
            }
            // 计算面积
            int width = right - left + 1;
            ans = Math.max(ans, cur * width);
        }
        return ans;
    }

    public static void main(String[] args) {
        Solution_84 solution = new Solution_84();
        int[] heights = { 2, 1, 5, 6, 2, 3 };
        int ans = solution.largestRectangleArea(heights);
        System.out.println(ans);
    }
}
